import java.util.Arrays;

public class Leet115 {
    public static void main(String[] args) {
        Leet115 l = new Leet115();
        System.out.println(l.numDistinct("babgbag","bag"));
    }
    public int numDistinct(String s, String t) {
        int sl = s.length(),tl = t.length();
        int[][] dp = new int[tl+1][sl+1];
        Arrays.fill(dp[0],1);
        for (int i = 1; i < tl+1; i++)
            for (int j = 1; j < sl+1; j++)
                dp[i][j] = t.charAt(i-1)==s.charAt(j-1)?dp[i][j-1]+dp[i-1][j-1]:dp[i][j-1];
        return dp[tl][sl];
    }
}
